0113. 路径总和 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS 回溯

1. 📝 题目描述

• leetcode

给你二叉树的根节点 root 和一个整数目标和 targetSum，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

---

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

---

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

2. 🎯 s.1 - DFS 回溯

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** g_ans;
int* g_colSizes;
int g_ansSize;
int g_path[5001];
int g_pathLen;

void dfs(struct TreeNode* node, int remain) {
    if (!node) return;
    g_path[g_pathLen++] = node->val;
    remain -= node->val;
    if (!node->left && !node->right && remain == 0) {
        g_ans[g_ansSize] = (int*)malloc(g_pathLen * sizeof(int));
        memcpy(g_ans[g_ansSize], g_path, g_pathLen * sizeof(int));
        g_colSizes[g_ansSize] = g_pathLen;
        g_ansSize++;
    }
    dfs(node->left, remain);
    dfs(node->right, remain);
    g_pathLen--;
}

int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes) {
    g_ans = (int**)malloc(5000 * sizeof(int*));
    g_colSizes = (int*)malloc(5000 * sizeof(int));
    g_ansSize = 0;
    g_pathLen = 0;
    dfs(root, targetSum);
    *returnSize = g_ansSize;
    *returnColumnSizes = g_colSizes;
    return g_ans;
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
  const ans = []

  const dfs = (node, remain, path) => {
    if (!node) return
    path.push(node.val)
    remain -= node.val
    if (!node.left && !node.right && remain === 0) {
      ans.push([...path])
    }
    dfs(node.left, remain, path)
    dfs(node.right, remain, path)
    path.pop()
  }

  dfs(root, targetSum, [])
  return ans
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ans = []

        def dfs(node: Optional[TreeNode], remain: int, path: List[int]) -> None:
            if not node:
                return
            path.append(node.val)
            remain -= node.val
            if not node.left and not node.right and remain == 0:
                ans.append(path[:])
            dfs(node.left, remain, path)
            dfs(node.right, remain, path)
            path.pop()

        dfs(root, targetSum, [])
        return ans

• 时间复杂度：$O(n^2)$，其中 $n$ 是节点数，每个节点访问一次，找到路径时复制需 $O(n)$
• 空间复杂度：$O(n)$，递归栈和路径数组的深度均为 $O(n)$（不计输出结果）

算法思路：

• 对二叉树进行 DFS，维护当前路径 path 和剩余目标值 remain
• 到达叶子节点时，若 remain == 0，将当前路径的副本加入结果
• 回溯时弹出末尾元素，恢复路径状态